import java.util.List;

public class KDTree implements PointSet{
    private static final boolean diviedByX = false;
    private static final boolean diviedByY = true;

    private class Node implements Comparable<Node> {
        private Node left;
        private Node right;
        private point p;
        private boolean orientation;
        public double bestDistanceToGoal = Double.MAX_VALUE;

        public Node(point p, boolean orientation) {
            this.p = p;
            this.orientation = orientation;
        }

        @Override
        public int compareTo(Node o) {
            if (this.orientation == diviedByX) {
                return Double.compare(this.p.getX(), o.p.getX());
            } else {
                return Double.compare(this.p.getY(), o.p.getY());
            }
        }
    }

    private Node root;

    public KDTree(List<point> points) {
        for (point p : points) {
            insert(p);
        }
    }
    public KDTree(){

    }

    public void insert(point p) {
        root = insert(root, p, diviedByX);
    }

    private Node insert(Node x, point p, boolean orientation) {
        if (x == null) return new Node(p, orientation);
        int cmp = x.compareTo(new Node(p, orientation));
        if (cmp < 0) x.left = insert(x.left, p, !orientation);
        else x.right = insert(x.right, p, !orientation);
        if (x.p.equals(p)) x.p = p;
        return x;
    }

    public point nearest(double x, double y) {
        return nearest(root, root, new point(null, x, y), diviedByX).p;
    }

    private Node nearest(Node x, Node best, point goal, boolean orientation) {
        if (x == null) return best;
        if (Double.compare(x.p.distanceTo(goal), best.bestDistanceToGoal) < 0) {
            best = x;
            best.bestDistanceToGoal = x.p.distanceTo(goal);
        }
        int cmp = x.compareTo(new Node(goal, orientation));
        Node goodSide = cmp < 0 ? x.left : x.right;
        Node badSide = cmp < 0 ? x.right : x.left;
        best = nearest(goodSide, best, goal, !orientation);
        if (isWorthLook(x, goal, best.bestDistanceToGoal, orientation))
            best = nearest(badSide, best, goal, !orientation);
        return best;
    }

    private boolean isWorthLook(Node curNode, point goal, double bestDistance, boolean orientation) {
        if (orientation == diviedByX)
            return goal.getX() - curNode.p.getX() < bestDistance;
        else
            return goal.getY() - curNode.p.getY() < bestDistance;
    }

}
